package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/27 9:36
 */
public class LC647回文子串 {

    public static int countSubstrings(String s) {
        return dynamicProgramming(s.toCharArray());
    }

    public static void main(String[] args) {
        String s = "abc";
        System.out.println(countSubstrings(s));
    }

    private static int dynamicProgramming(final char[] array) {
        //dp[i][j]代表区间array[i, j]字符串是否是回文子串
        boolean[][] dp = new boolean[array.length][array.length];
        int answer = 0;
        for (int i = dp.length - 1; i >= 0; i--) {
            for (int j = i; j < dp[0].length; j++) {       //因为状态转移方程式依赖于左下角，因此只能从左到右，从下到上遍历
                if (array[i] != array[j]) continue;             //默认就是false，不相等不是回文子串时不需要进行操作
                //单个字符必是回文子串
                if (j - i <= 1 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    answer++;
                }
            }
        }
        Arrays.stream(dp).forEach(item -> System.out.println(Arrays.toString(item)));
        return answer;
    }

    private static int doubleIndex(final char[] array) {
        int answer = 0;
        for (int i = 0; i < array.length; i++) {
            answer += expansion(array, i, i);
            answer += expansion(array, i, i + 1);
        }
        return answer;
    }

    /**
     * 在数组中以i或者以i和i+1为中心点进行向两边扩散并统计回文子串个数
     */
    private static int expansion(final char[] array, int i, int j) {
        int res = 0;
        while (i >= 0 && j < array.length && array[i] == array[j]) {
            i--;        //i向左边扩散
            j++;        //j向右边扩散
            res++;
        }
        return res;
    }

}
